import java.util.Comparator;
import java.util.PriorityQueue;

class MedianFinder {
    public PriorityQueue<Integer> min = new PriorityQueue<>();
    public PriorityQueue<Integer> max = new PriorityQueue<>(new Comparator<Integer>() {
        @Override
        public int compare(Integer o1, Integer o2) {
            return o2 - o1;
        }
    });

    /** initialize your data structure here. */
    public MedianFinder() {
    }

    public void addNum(int num) {
        if (min.isEmpty() && max.isEmpty()) {
            max.add(num);
        } else {
            if (num <= max.peek()) {
                max.add(num);
            } else {
                min.add(num);
            }
            if (Math.abs(min.size() - max.size()) > 1) {
                if (min.size() > max.size()) {
                    max.add(min.poll());
                } else {
                    min.add(max.poll());
                }
            }
        }

    }

    public double findMedian() {
        if (max.size() == min.size()) return ((max.peek() + min.peek()) / 2.0);
        return (max.size() > min.size() ? max : min).peek();
    }
}
